instance

• given a database schema \(\mathcal{C} = (G, \simeq)\), an instance on \(\mathcal{C}\) is a bunch of tables whose data conform to the specified layout
  • \(G = (V, A, src, tgt)\)
• denote \((\text{PK}, \text{FK}): \mathcal{C} \to \mathbf{Set}\)
  • consituents:
    • A: primary ID part
      • a function \(\text{PK}: V \to \mathbf{Set}\), sending each vertex \(v \in V\) to a set \(\text{PK}(v)\)
    • B: foreign ID part
      • for every arrow \(a \in A\) where \(v = src(a) \in V\) and \(w = tgt(a) \in V\), a function \(\text{FK}(a): \text{PK(v)} \to \text{PK(w)}\)
      • each foreign key relation is a function that maps primary key values in one table to the primary key in another table
  • laws: preservation of congruence
    • ...
    • the congruence (declared on the paths on graph) is preserved